package Demo1;

import java.util.LinkedList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 34255
 * Date: 2024-08-23
 * Time: 14:39
 */
public class Test {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    //二叉树的最小深度
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        int leftMinDepth = minDepth(root.left);
        int rightMinDepth = minDepth(root.right);
        if(leftMinDepth != 0 && rightMinDepth != 0){
            return Math.min(leftMinDepth,rightMinDepth) + 1;
        }else if(leftMinDepth == 0){
            return rightMinDepth + 1;
        }else{
            return leftMinDepth + 1;
        }
    }

    //路径总和
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) return false;

        //判段是否为叶子节点
        if(root.left == null && root.right == null && targetSum == root.val) return true;

        //先判段左树
        boolean ret = hasPathSum(root.left,targetSum - root.val);
        if(ret) return true;

        //判段右树
        ret = hasPathSum(root.right,targetSum - root.val);
        if(ret) return true;

        return false;
    }

    //二叉树的所有路径
    public List<String> list = new LinkedList<String>();

    public void LinkedString(TreeNode root,String str){
        if(root == null) return;

        //判段叶子节点
        if(root.left == null && root.right == null){
            str += root.val;
            list.add(str);
            return;
        }

        str = str + root.val + "->";

        LinkedString(root.left,str);

        LinkedString(root.right,str);
    }
    public List<String> binaryTreePaths(TreeNode root) {
        LinkedString(root,"");
        return list;
    }

    public static void main(String[] args) {

    }
}
